package wtx.geek;

import com.google.common.collect.Lists;

import java.util.*;
import java.util.Random;

/**
 * Given an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.
 * * The sub-arrays should not overlap.
 *
 * eg-   [2 -1 -2 1 -4 2 8]
 * ans - (-1 -2 1 -4) (2 8), diff = 16
 *
 * https://careercup.com/question?id=19286747
 *
 */

public class Solution {
    enum SumType {
        LeftMax,
        LeftMin,
        RightMax,
        RightMin
    }
    static class Range {
        int left, right, _left, _right;
        int sum, _sum;
        SumType stype;
        Range(SumType t, int pos) {
           stype = t;
           switch (stype) {
               case LeftMax:
                   sum = Integer.MIN_VALUE;
                   left = _left = pos;
                   right = _right = pos;
                   break;
               case LeftMin:
                   left = _left = pos;
                   right = _right = pos;
                   sum = Integer.MAX_VALUE;
                   break;
               case RightMax:
                   left = _left = pos;
                   right = _right = pos;
                   sum = Integer.MIN_VALUE;
                   break;
               case RightMin:
                   left = _left = pos;
                   right = _right = pos;
                   sum = Integer.MAX_VALUE;
                   break;
           }
        }
        Range(Range other) {
            this.left = other.left;
            this.right = other.right;
            this._left = other._left;
            this._right = other._right;
            this.sum = other.sum;
            this._sum = other._sum;
            this.stype = other.stype;
        }
        void add(int pos, int v) {
            switch (stype) {
                case LeftMax:
                    _sum += v;
                    if (_sum < 0) {
                        if (sum < _sum) {
                            sum = _sum;
                            left = _left;
                            right = pos+1;
                        }
                        _sum = 0;
                        _left = pos+1;
                        _right = pos+2;
                    } else if (_sum > sum) {
                        left = _left;
                        right = pos+1;
                        sum = _sum;
                    }
                    break;
                case LeftMin:
                    _sum += v;
                    if (_sum > 0) {
                        if (sum > _sum) {
                            sum = _sum;
                            left = _left;
                            right = pos + 1;
                        }
                        _sum = 0;
                        _left = pos+1;
                        _right = pos+2;
                    } else if (_sum < sum) {
                        left = _left;
                        right = pos + 1;
                        sum = _sum;
                    }
                    break;
                case RightMax:
                    _sum += v;
                    if (_sum < 0) {
                        if (sum < _sum) {
                            sum = _sum;
                            right = _right;
                            left = pos;
                        }
                        _sum = 0;
                        _left = pos-1;
                        _right = pos;
                    } else if (_sum > sum) {
                        right = _right;
                        left = pos;
                        sum = _sum;
                    }
                    break;
                case RightMin:
                    _sum += v;
                    if (_sum > 0) {
                        if (sum > _sum) {
                            sum = _sum;
                            right = _right;
                            left = pos;
                        }
                        _sum = 0;
                        _left = pos-1;
                        _right = pos;
                    } else if (_sum < sum) {
                        right = _right;
                        left = pos;
                        sum = _sum;
                    }
                    break;
            }
        }

        @Override
        public String toString() {
            return String.format("%s|[%d, %d](%d, %d) sum = %d(%d)", stype.toString(), left, right, _left, _right, sum, _sum);
        }
    }
    public static int[] findMaxSplit(int[] array) {
        int[] ret = new int[4];
        Range[][] arrayInfo = new Range[array.length][4];
        Range leftMax = new Range(SumType.LeftMax, 0);
        Range leftMin = new Range(SumType.LeftMin, 0);
        leftMax.add(0, array[0]);
        leftMin.add(0, array[0]);
        arrayInfo[0][0] = leftMax;
        arrayInfo[0][1] = leftMin;
        for (int i = 1; i < array.length-1; ++i) {
            Range leftMax1 = new Range(arrayInfo[i-1][0]);
            leftMax1.add(i, array[i]);
            arrayInfo[i][0] = leftMax1;
            Range leftMin1 = new Range(arrayInfo[i-1][1]);
            leftMin1.add(i, array[i]);
            arrayInfo[i][1] = leftMin1;
        }
        Range rightMax = new Range(SumType.RightMax, array.length);
        Range rightMin = new Range(SumType.RightMin, array.length);
        rightMax.add(array.length-1, array[array.length-1]);
        rightMin.add(array.length-1, array[array.length-1]);
        arrayInfo[array.length-1][2] = rightMax;
        arrayInfo[array.length-1][3] = rightMin;
        for (int i = array.length-2; i > 0; --i) {
            Range rightMax1 = new Range(arrayInfo[i+1][2]);
            rightMax1.add(i, array[i]);
            arrayInfo[i][2] = rightMax1;
            Range rightMin1 = new Range(arrayInfo[i+1][3]);
            rightMin1.add(i, array[i]);
            arrayInfo[i][3] = rightMin1;
        }
        int maxDiff = 0;
        for (int i = 0; i < array.length-1; ++i) {
            Range[] leftRanges = arrayInfo[i],
                    rightRanges = arrayInfo[i+1];
            int m1 = leftRanges[0].sum - rightRanges[3].sum;
            int m2 = rightRanges[2].sum - leftRanges[1].sum;
            if (m1 > m2) {
                if (m1 > maxDiff) {
                    maxDiff = m1;
                    ret[0] = leftRanges[0].left;
                    ret[1] = leftRanges[0].right-1;
                    ret[2] = rightRanges[3].left;
                    ret[3] = rightRanges[3].right-1;
                }
            } else {
                if (m2 > maxDiff) {
                    maxDiff = m2;
                    ret[0] = leftRanges[1].left;
                    ret[1] = leftRanges[1].right-1;
                    ret[2] = rightRanges[2].left;
                    ret[3] = rightRanges[2].right-1;
                }
            }
        }
        return ret;
    }
}
